package com.linchong.stackqueue.medium;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-12-01 16:02
 * @Description: ValidSequence$合法的出栈序列
 * <p>
 * 已知从1至n的数字序列，按顺序入栈，每个数字入栈即可出栈，也可以在栈中停留，
 * 等待后面的数字入栈出栈后，该数字在出栈，求该数字序列的出栈序列是否合法？
 * <p>
 * poj 1363
 * <p>
 * eg:
 * 1 2 3 4 5
 * <p>
 * 3 2 5 4 1 合法
 * 3 1 2 4 5 非法
 * https://leetcode-cn.com/problems/validate-stack-sequences/
 * <p>
 * 使用一个栈来模拟
 * O(n)，元素只入栈一次
 */
@SuppressWarnings("unused")
public class ValidSequence {


	public boolean validateStackSequences(int[] pushed, int[] popped) {
		Stack<Integer> stack = new Stack<>();
		int index=0;
		for (int value : pushed) {
			stack.push(value);
			while (!stack.isEmpty() && stack.peek() == popped[index]) {
				stack.pop();
				index++;
			}
		}
		return stack.isEmpty();
	}

}





















